package algorithms.sort;

import java.util.Arrays;

import algorithms.Util;

/**
 * 希尔排序是可变增量的插入排序，普通插入排序的增量为1；<br>
 * 在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。<br>
 * 然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。<br>
 * 
 * @author shaoyuxia
 *
 * @param <T>
 */

public class ShellSort<T extends Comparable<T>> implements ISort<T> {

	@Deprecated
	T[] sort_original(T[] a) {
		for (int gap = a.length / 2; gap > 0; gap /= 2) {
			for (int i = gap; i < a.length; i += gap) {// 根据gap分组，a[i]是待插入对象，a[i]之前的是有序序列
				T tmp = a[i];
				// 这边有问题j从0开始+gap，会丢失1+gap的情况，而这些丢失的情况，都会交给gap=1处理
				for (int j = 0; j < i; j += gap) {// 有序序列和a[i]比较，判断a[i]是否要插入
					if (a[i].compareTo(a[i - gap]) > 0) {
						break;
					}
					if (a[i].compareTo(a[j]) < 0) {
						// insert
						Util.rightMove(a, j, i - gap, gap);
						a[j] = tmp;
						break;
					}
				}
			}
		}
		return a;
	}

	T[] sort_original_modify(T[] a) {
		int length = a.length;
		for (int gap = length / 2; gap > 0; gap /= 2) {
			for (int i = 0; i <= gap; i++) {// 组头
				// 分组内的插入排序
				for (int j = i + gap; j < length; j += gap) {
					// 判断是否需要插入，如果比有序序列最大值小，则需要被插入到有序序列中去
					if (a[j].compareTo(a[j - gap]) < 0) {
						T tmp = a[j];
						/*
						 * 这里使用的是从有序序列的头开始比较来寻找合适位置，找到后移动数组，插入元素； 数组只会移动一次，性能较差
						 * 
						 */
						for (int k = i; k < j; k += gap) {
							if (a[j].compareTo(a[k]) < 0) {
								Util.rightMove(a, k, j - gap, gap);
								a[k] = tmp;
							}
						}
					}

				}
			}
			// System.out.print("gap=" + gap + " :");
			// Util.print(a);
		}
		return a;
	}

	T[] sort_Enhance(T[] a) {
		for (int gap = a.length / 2; gap > 0; gap /= 2) {
			for (int i = 0; i < gap; i++) {// 根据gap分组，选出组头元素
				for (int j = i + gap; j < a.length; j += gap) {
					// 判断当前待插入元素是否比有序序列的最大元素小，小则代表需要插入到有序序列中
					if (a[j].compareTo(a[j - gap]) < 0) {
						T temp = a[j];
						int k = j - gap;
						/*
						 * 移动数组,边移动边比较，是一种反向遍历比较（待插入数据从此元素向前比较，
						 * 找到比自己小的就在小的之后插入，和从有序序列数组头开查询相反，
						 * 从头扫描是遍历比较，当找到比自己大的，就在大的之前插入； 数组会移到多次，直到找到合适位置 性能很好
						 */
						while (k >= 0 && a[k].compareTo(temp) > 0) {
							a[k + gap] = a[k];
							k -= gap;
						}
						a[k + gap] = temp;
					}
				}

			}
		}
		return a;
	}

	@Override
	public T[] sort(T[] a) {
		return sort_Enhance(a);
	}

	public static void main(String[] args) {
		ShellSort<Integer> s = new ShellSort<>();
		Integer[] array = Util.generateArray(500000);
		// array = new Integer[] { 5, 4, 3, 2, 1 };
		Integer[] arraycopy = Arrays.copyOf(array, array.length);
		// Integer[] arraycopy2 = Arrays.copyOf(array, array.length);
		Util.print(array, 30);

		long begin = System.currentTimeMillis();
		s.sort_original_modify(array);
		System.out.println("used :" + (System.currentTimeMillis() - begin));

		Util.print(array, 30);
		//
		Util.print(arraycopy, 30);

		begin = System.currentTimeMillis();
		s.sort_Enhance(arraycopy);
		System.out.println("used :" + (System.currentTimeMillis() - begin));

		Util.print(arraycopy, 30);

	}
}
